/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/course-schedule-ii
   @Language: C++
   @Datetime: 20-01-07 16:18
   */

// Method 1, Topological Sort. 
class Solution {
public:
	vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
		vector<list<int> > edges(numCourses, list<int>());
		vector<int> indegrees(numCourses, 0);
		for(const auto &v:prerequisites){
			edges[v[1]].push_back(v[0]);
			++indegrees[v[0]];
		}
		queue<int> courses;
		for(int i=0; i<numCourses; ++i)
			if (indegrees[i]==0) courses.push(i);
		vector<int> order;
		for(; !courses.empty(); --numCourses, courses.pop()){
			order.push_back(courses.front());
			for(const auto &node:edges[courses.front()])
				if(--indegrees[node]==0) courses.push(node);
		}
		return numCourses?vector<int>():order;
	}
};
